/**
 * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
 *
 * 示例 1：
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 *
 * 示例 2：
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 *
 * 示例 3：
 * 输入：nums = [], target = 0
 * 输出：[-1,-1]
 *
 * 提示：
 * 0 <= nums.length <= 105
 * -109 <= nums[i] <= 109
 * nums 是一个非递减数组
 * -109 <= target <= 109
 */

/**
 * 1.直接二分查找, 在找到对应的数后, 使用双指针来遍历和找到的数的相同的数
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 *
 * 2. 为了满足时间复杂度的需求, 我们要改进方法, 怎么改进呢, 我们分两次来二分查找
 * 我们所需的数, 因为我们要查找的边界上的数, 所以我们在找第一个数的时候, 在改变左
 * 边界的时候条件要取等, 同样的, 我们在取中间值的时候要取靠左边的一个,, 要是取靠
 * 左边的一个我们在得到等的时候就会改变不了边界, 要是我们要改变边界就要是 right - 1
 * 这样就会使我们得不到想要的左边第一个数
 * 我们在找第二个数的时候, 在改变右边界的时候条件我们要取等, 并且取靠右边的数,
 * 也是和上边同理
 * 时间复杂度 : O(log n)
 * 空间复杂度 : O(1)
 */

public class Main {

    // 1. 直接二分查找
    public int[] searchRange1(int[] nums, int target) {

        // 数组长度
        int n = nums.length;

        // 二分查找两边边界
        int left = 0, right = n - 1;

        // 最普通的二分查找
        while (left <= right) {

            int mid = (left + right) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {

                // 从中间向两边遍历
                left = mid;
                right = mid;

                while (left >= 0 && nums[left] == target) {
                    left--;
                }

                while (right < n && nums[right] == target) {
                    right++;
                }

                // 因为在判断的时候我们多用了一个位置, 所以我们要退一个位置
                return new int[]{left + 1, right - 1};
            }
        }

        // 没找到返回 -1, -1
        return new int[]{-1, -1};
    }

    // ************************************************************
    // 2. 两边分别查找
    public int[] searchRange(int[] nums, int target) {

        // 数组长度
        int n = nums.length;

        // 初始化数组
        int[] arr = new int[]{-1, -1};

        // 判断特别的 n 为零
        if (n == 0) {
            return arr;
        }

        // 二分边界
        int left = 0, right = n - 1;

        // 第一个数
        while (left < right) {

            // 这里取靠左边的数
            int mid = (left + right) / 2;

            if (nums[mid] < target) {
                left = mid + 1;
            } else {

                // 改变右边界的时候这里要加上等于, 且不能 -1
                right = mid;
            }
        }

        // 这里要是没有找到, 就说明没有这个数
        if (nums[left] == target) {

            // 找到第一个数
            arr[0] = left;
        } else {

            // 没找到返回 -1, -1
            return arr;
        }

        // 重置边界
        left = 0;
        right = n - 1;

        // 第二个数
        while (left < right) {

            // 这里取靠右边的数
            int mid = (left + right + 1) / 2;
            if (nums[mid] <= target) {

                // 改变有边界的时候这里要加上等于, 且不能 +1
                left = mid;

            } else {
                right = mid - 1;
            }
        }

        // 这里肯定可以找到
        arr[1] = left;

        // 返回数组
        return arr;
    }
}